package 剑指offer;

import java.util.Stack;

public class offer {

    /**
     * 03.找出数组中重复的数字。
     *
     *
     * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
     *
     * 示例 1：
     *
     * 输入：
     * [2, 3, 1, 0, 2, 5, 3]
     * 输出：2 或 3
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int findRepeatNumber(int[] nums) {
        int n[]=new int[nums.length];
        for (int i=0;i<nums.length;i++) {
            if (n[nums[i]]==0){
                n[nums[i]]++;
            }else {
                return nums[i];
            }
        }
        return -1;
    }

    /**
     * 04.在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     *
     *  
     *
     * 示例:
     *
     * 现有矩阵 matrix 如下：
     *
     * [
     *   [1,   4,  7, 11, 15],
     *   [2,   5,  8, 12, 19],
     *   [3,   6,  9, 16, 22],
     *   [10, 13, 14, 17, 24],
     *   [18, 21, 23, 26, 30]
     * ]
     * 给定 target = 5，返回 true。
     *
     * 给定 target = 20，返回 false。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length==0||matrix[0].length==0||matrix == null||matrix[0] == null){
            return false;
        }
        int n=matrix.length;
        int m=matrix[0].length;
        int i=0,j=m-1;
        while (i<n&&j>=0){
            if (matrix[i][j]==target)
                return true;
            if (matrix[i][j]>target){
                j--;
            }else {
                i++;
            }
        }
        return false;
    }

    /**
     * 05.请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：s = "We are happy."
     * 输出："We%20are%20happy."
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param s
     * @return
     */
    public String replaceSpace(String s) {
        return s.replaceAll(" ","%20");
    }

    /**
     * 06.输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
     *
     *
     *
     * 示例 1：
     *
     * 输入：head = [1,3,2]
     * 输出：[2,3,1]
     * @param head
     */
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack=new Stack<ListNode>();
        while (head!=null){
            stack.push(head);
            head=head.next;
        }
        int size=stack.size();
        int result[]=new int[size];
        for (int i=0;i<size;i++){
            result[i]=stack.pop().val;
        }
        return result;
    }
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }


    public static void main(String[] args) {
        int nums[]={2, 3, 1, 0, 2, 5, 3};
        offer offer = new offer();
        System.out.println(offer.findRepeatNumber(nums));

        int nums2[][]={
                {1,4,7,11,15},
                {2,5,8,12,19},
                {3,6,9,16,22},
                {10,13,14,17,24},
                {18,21,23,26,30}};
        System.out.println(offer.findNumberIn2DArray(nums2, 5));

        System.out.println(offer.replaceSpace("wo fsa   fsdf"));
    }

}
